package leetcode.editor.cn;

import java.util.Arrays;

/**
 * @author: yangwk
 * @date: 2023/6/6
 * @description:
 **/
public class P740DeleteandEarn {
    /**
     * You are given an integer array nums. You want to maximize the number of points you get
     * by performing the following operation any number of times:
     * <p>
     * Pick any nums[i] and delete it to earn nums[i] points. Afterwards, you must delete every
     * element equal to nums[i] - 1 and every element equal to nums[i] + 1.
     * Return the maximum number of points you can earn by applying the above operation some
     * number of times.
     */
    public static void main(String[] args) {
        System.out.println(deleteAndEarn(new int[]{8, 3, 4, 7, 6, 6, 9, 2, 5, 8, 2, 4, 9, 5, 9, 1, 5, 7, 1, 4}));
    }

    public static int deleteAndEarn(int[] nums) {
        int maxVal = 0;
        for (int val : nums) {
            maxVal = Math.max(maxVal, val);
        }
        int[] sum = new int[maxVal + 1];
        for (int val : nums) {
            sum[val] += val;
        }
        return rob(sum);
    }

    public static int rob(int[] nums) {
        int size = nums.length;
        int first = nums[0], second = Math.max(nums[0], nums[1]);
        for (int i = 2; i < size; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }

}
